package com.exercises;

import com.alibaba.fastjson.JSONObject;
import org.w3c.dom.NodeList;

import java.io.ByteArrayInputStream;
import java.io.InputStream;
import java.lang.reflect.Array;
import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.Stream;

public class Exercise24 {

    public static void main(String[] args) {
        System.out.println(JSONObject.toJSONString(new Exercise24().findSubstring("wordgoodgoodgoodbestword", new String[]{"word","good","best","good"})));
    }

    public List<Integer> findSubstring(String s, String[] words) {
        if (s == null || words == null || words.length == 0)
            return new ArrayList<>();
        int wordLen = words[0].length();
        int len = words.length;
        int totalLen = wordLen * len;
        HashMap<String, Integer> map = new HashMap<>();
        HashMap<String, Integer> map2 = new HashMap<>();
        //把数组处理为Map提高检索速度
        for (String word : words) {
            if (map.containsKey(word)) {
                Integer value = map.get(word);
                value++;
                map.put(word, value);
            } else {
                map.put(word, 1);
            }
        }
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < wordLen; i++) {
            int index = i;
            for (int j = i; j + wordLen <= s.length(); j += wordLen) {
                String blok = s.substring(j, j + wordLen);
                if (!map.containsKey(blok)) {
                    map2.clear();
                    index = j + wordLen;
                } else {
                    Integer count = map2.get(blok) == null ? 0 : map2.get(blok);
                    if (map.get(blok).equals(count)) {
                        String first;
                        while (!(first = s.substring(index, index + wordLen)).equals(blok)) {
                            map2.put(first, map2.get(first) - 1);
                            index += wordLen;
                        }
                        index += wordLen;
                    } else {
                        map2.put(blok, count + 1);
                    }
                    if (j + wordLen - index == totalLen) {
                        res.add(index);
                        String firstWord = s.substring(index, index + wordLen);
                        map2.put(firstWord, map2.get(firstWord) - 1);
                        index += wordLen;
                    }
                }
            }
            map2.clear();

        }
        return res;
    }
}
